package algorithmic_data_structure.快排.mycode;

/**
 * 给出一个数组，要求以数组中最后的元素X作为划分值将数组划分为两部分，最后X在中间
 *
 * x有可能会重复
 */
public class Partition {
    
    public static void main(String[] args) {
        int[] array = {
//          1,3,5,4,7,1,3,5,1,3,6,4,5,7,8,9,1,35,3,5,5,4,3,2,1,6,6,4,8,6,3,1,35,3,3,5,45,12,6,9
                1,2,3,4,5,4,3,2,1,5,3
        };
        partition(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " , ");
        }
    }

    /**
     * 将当前数组划分为三部分，其中返回的数组即是中间数组的两端（中间数组就是相等划分值组成的）
     */
    public static int[] partition(int[] array, int left, int right) {
        if (left > right)
        {
            return new int[]{-1,-1};
        }
        if (left == right)
        {
            return new int[]{left,right};
        }

        int x = array[right];
        // 左边界
        int leftSide = left - 1;
        // 右边界(最右边的划分值X占据一个位置)
        int rightSide = right;

        int index = left;

        while (index < rightSide)
        {
            if (array[index] == x)
            {
                index++;
            }
            else if (array[index] < x)
            {
                Partition.swap(array,leftSide + 1,index);
                leftSide++;
                index++;
            }
            else
            {
                Partition.swap(array,rightSide - 1,index);
                rightSide--;
            }
        }

        swap(array,rightSide++,right);
//        Partition.swap(array,right,index);
//        // 这里rightSide不-1是因为最后index会移动到右边界前面，而index还会和划分值x进行交换，即相当于右边界加一（而实际上没有加）
//        // 可以根据X没有重复的情况下进行推导会好理解很多
        return  new int[]{leftSide + 1,rightSide - 1};
    }

    public static void partition(int[] array)
    {
        if (array == null || array.length <= 1)
        {
            return;
        }

        int len = array.length;
        int x = array[len - 1];

        //小于划分值的左部，包住比X小的数（小于 x区），一开始在数组 最左-1 的位置
        int left = -1;
        //大于等于划分值的右部，包住大于或等于X的数（大于等于 x区），一开始在最右-1 的位置(先将x所在的位置包进去)
        //这里为什么是len - 1?
        //A： 因为X所在的位置就已经占据了一个位置，此时最右的下标为len - 2,因为是作为边界不能取到（就像左边界一样）所以要加一
        //   即len - 2 + 1
        int right = len - 1;

        /*
            其中中部 index ~ left 这一部分就是等于X的部分了
         */

        int index = 0;

        //遍历的下标不能到达 右部
        while (index < right)
        {
            if (array[index] == x)
            {
                index++;
            }
            else if (array[index] < x)
            {
                swap(array,left + 1,index);
                index++;
                left++;
            }
            else
            {
                //注意这里index不能动，因为只是将当前index的元素扩进(交换)右部，但是交换到index上的元素还没检查过的，所以index是不能变的
                swap(array,right - 1,index);
                right--;
            }
        }

        swap(array,len - 1,index);
    }

    public static void swap(int[] array, int i, int j) {
        if (i == j){
            return;
        }
        array[i] += array[j];
        array[j] = array[i] - array[j];
        array[i] = array[i] - array[j];
    }
}
